package heap;

import beans.ListNode;

/**
 * @author pengfei.hpf
 * @date 2020/2/29
 * @verdion 1.0.0
 * 23. 合并K个排序链表
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 *
 * 示例:
 *
 * 输入:
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 */
public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null){
            return null;
        }
        ListNode head = new ListNode(1);
        ListNode tail = head;
        while(tail != null){
            ListNode min = null;
            int minVal = Integer.MAX_VALUE;
            int minIndex = -1;
            for(int i = 0 ; i< lists.length; i ++){
                if(lists[i] != null && lists[i].val < minVal){
                    min = lists[i];
                    minVal = lists[i].val;
                    minIndex = i;
                }
            }
            if(minIndex >=0){
                lists[minIndex] = min.next;
            }
            tail.next = min;
            tail = tail.next;
        }
        return head.next;
    }
}
